package com.gjx.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
//102. 二叉树的层次遍历
//
//给定一个二叉树，返回其按层次遍历的节点值。 （即逐层地，从左到右访问所有节点）。
//
//例如:
//给定二叉树: [3,9,20,null,null,15,7],
//
//    3
//   / \
//  9  20
//    /  \
//   15   7
//返回其层次遍历结果：
//
//[
//  [3],
//  [9,20],
//  [15,7]
//]
import java.util.Queue;



public class Solution102 {
	public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if (root == null) {
        	return res;
        }
        
        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.offer(root);
        
        while (!queue.isEmpty()) {
        	int size = queue.size();
        	
        	List<Integer> list = new ArrayList<>();
        	for (int i=0; i<size; i++) {
        		TreeNode tn = queue.poll();
        		list.add(tn.val);
        		if (tn.left != null) {
        			queue.offer(tn.left);
        		}
        		if (tn.right != null) {
        			queue.offer(tn.right);
        		}
        	}
        	res.add(list);
        }
        
        return res;
    }
}
